import java.util.HashMap;

public class CanIWin {

    public static void main(String[] args) {
        CanIWin canIWin = new CanIWin();
        System.out.println(canIWin.canIWin(5,50));
    }

    HashMap<Integer, Boolean> map = new HashMap<>();
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (desiredTotal == 0) return true;
        if ((maxChoosableInteger + 1) * maxChoosableInteger / 2 < desiredTotal) return false;
        return dfs(maxChoosableInteger, desiredTotal, 0, 0);
    }

    public boolean dfs(int maxChoosableInteger, int desiredTotal, int sum, int usedNum) {
        if (!map.containsKey(usedNum)) {
            boolean temp = false;
            for (int i = 0; i < maxChoosableInteger; i++) {
                if (((usedNum >> i) & 1) == 0) {
                    if (sum + 1 + i >= desiredTotal || (!dfs(maxChoosableInteger, desiredTotal, sum + 1 + i, usedNum | (1 << i)))) {
                        temp = true;
                        break;
                    }
                }
            }
            map.put(usedNum, temp);
        }
        return map.get(usedNum);
    }
}
